package findKth

import ()

//func FindKth(a []int, n int, K int) int {
//	b := QuickSort(a, 0, len(a)-1, K)
//	return b[n-K]
//}
//
//func QuickSort(list []int, begin, end int, K int) []int {
//	if begin < end {
//		loc, err := partition(list, begin, end)
//		if err != nil {
//			fmt.Printf("partition error: %s", err.Error())
//		}
//		QuickSort(list, begin, loc-1, K)
//
//		QuickSort(list, loc+1, end, K)
//	}
//	return list
//}
//
//func partition(list []int, begin, end int) (i int, err error) {
//	i = begin + 1
//	j := end
//	for i < j {
//		if list[i] > list[begin] {
//			list[i], list[j] = list[j], list[i]
//			j--
//		} else {
//			i++
//		}
//	}
//	if list[i] >= list[begin] {
//		i--
//	}
//	list[begin], list[i] = list[i], list[begin]
//	return
//}
func FindKth2(a []int, n int, K int) int {
	// write code here
	mid, i := a[0], 1
	first, tail := 0, n-1
	for first < tail {
		if a[i] < mid {
			a[i], a[tail] = a[tail], a[i]
			tail--
		} else {
			a[i], a[first] = a[first], a[i]
			first++
			i++
		}
	}
	a[first] = mid

	if K-1 == first {
		return mid
	}
	if K-1 < first {
		return FindKth2(a[:first], first, K)
	}
	return FindKth2(a[first+1:], n-first-1, K-first-1)
}
